{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pour Water Between Buckets to Make Water Levels Equal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: equalizeWater"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通过倒水操作让所有的水桶所含水量相等"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有 <code>n</code> 个水桶，每个水桶中所含的水量用一个 <b>下标从 0 开始</b>&nbsp;的数组 <code>buckets</code> 给出，第 <code>i</code> 个水桶中有 <code>buckets[i]</code> 升水。</p>\n",
    "\n",
    "<p>你想让所有的水桶中所含的水量相同。你可以从一个水桶向其它任意一个水桶倒任意数量的水（可以不是整数）。但是，你每倒 <code>k</code> 升水，<strong>百分之</strong> <code>loss</code> 的水会洒掉。</p>\n",
    "\n",
    "<p>请返回经过倒水操作，所有水桶中的水量相同时，每个水桶中的 <strong>最大</strong> 水量。如果你的答案和标准答案的误差不超过 <code>10<sup>-5</sup></code>，那么答案将被通过。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> buckets = [1,2,7], loss = 80\n",
    "<strong>输出:</strong> 2.00000\n",
    "<strong>解释:</strong> 从水桶 2 向水桶 0 倒 5 升水。\n",
    "5 * 80% = 4 升水会洒掉，水桶 0 只会获得 5 - 4 = 1 升水。\n",
    "此时所有的水桶中都含有 2 升水，所以返回 2。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> buckets = [2,4,6], loss = 50\n",
    "<strong>输出:</strong> 3.50000\n",
    "<strong>解释:</strong> 从水桶 1 向水桶 0 倒 0.5 升水。\n",
    "0.5 * 50% = 0.25 升水会洒掉，水桶 0 只会获得 0.5 - 0.25 = 0.25 升水。\n",
    "此时, buckets = [2.25, 3.5, 6].\n",
    "\n",
    "从水桶 2 向水桶 0 倒 2.5 升水。\n",
    "2.5 * 50% = 1.25 升水会洒掉，水桶 0 只会获得 2.5 - 1.25 = 1.25 升水。\n",
    "此时所有的水桶中都含有 3.5 升水，所以返回 3.5。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> buckets = [3,3,3,3], loss = 40\n",
    "<strong>输出:</strong> 3.00000\n",
    "<strong>解释:</strong> 所有的水桶已经含有相同的水量。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= buckets.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= buckets[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= loss &lt;= 99</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pour-water-between-buckets-to-make-water-levels-equal](https://leetcode.cn/problems/pour-water-between-buckets-to-make-water-levels-equal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pour-water-between-buckets-to-make-water-levels-equal](https://leetcode.cn/problems/pour-water-between-buckets-to-make-water-levels-equal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,7]\\n80', '[2,4,6]\\n50', '[3,3,3,3]\\n40']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "\n",
    "        def canDo(x):\n",
    "            need = have = 0\n",
    "            for bucket in buckets:\n",
    "                if bucket <= x:\n",
    "                    need += (x - bucket)\n",
    "                else:\n",
    "                    have += (bucket - x)\n",
    "            if need > have * (100 - loss) / 100:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        left, right = min(buckets), max(buckets)\n",
    "        while left < right - 10 ** (-5):\n",
    "            mid = (left + right) / 2\n",
    "            if canDo(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 二分\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n, l, r = len(buckets), 0, max(buckets)\n",
    "\n",
    "        def helper(x):\n",
    "            s1 = s2 = 0\n",
    "            for b in buckets:\n",
    "                if b > x:\n",
    "                    # 倒掉了多少水\n",
    "                    s1 += b - x\n",
    "                else:\n",
    "                    # 至少需要多少水\n",
    "                    s2 += (x - b) * 100 / (100 - loss)\n",
    "\n",
    "            return s1 >= s2\n",
    "\n",
    "\n",
    "        while (r - l) > 1e-5:\n",
    "            mid = (l + r) / 2\n",
    "            if helper(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "\n",
    "        return l\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n = len(buckets)\n",
    "        tot = sum(buckets)\n",
    "        l, r = 0, tot / n\n",
    "        eps = 10 ** (-6)\n",
    "        \n",
    "        def check(x):\n",
    "            a = b = 0 \n",
    "            \n",
    "            for i in buckets:\n",
    "                if i >= x:\n",
    "                    a += i - x \n",
    "                else:\n",
    "                    b += (x - i) / (100 - loss) * 100\n",
    "            if a >= b:\n",
    "                return True \n",
    "            return False \n",
    "        \n",
    "        while r - l > eps:\n",
    "            mid = (l + r) / 2 \n",
    "            if check(mid):\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid \n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "\n",
    "        def canDo(x):\n",
    "            need = have = 0\n",
    "            for bucket in buckets:\n",
    "                if bucket <= x:\n",
    "                    need += (x - bucket)\n",
    "                else:\n",
    "                    have += (bucket - x)\n",
    "            if need > have * (100 - loss) / 100:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        left, right = min(buckets), max(buckets)\n",
    "        while left < right - 10 ** (-5):\n",
    "            mid = (left + right) / 2\n",
    "            if canDo(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n = len(buckets)\n",
    "        s = sum(buckets)\n",
    "        if loss == 0:\n",
    "            return s / n\n",
    "        \n",
    "        def check(x):\n",
    "            pour_out = 0\n",
    "            pour_in = 0\n",
    "            for i in buckets:\n",
    "                if i < x:\n",
    "                    pour_in += x - i \n",
    "                else:\n",
    "                    pour_out += i - x \n",
    "            return pour_out * (1 - loss / 100) >= pour_in\n",
    "        \n",
    "        low, high = min(buckets), s / n \n",
    "        ans = low \n",
    "        while low <= high - 10 ** -5:\n",
    "            mid = (low + high) / 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 10 ** -6\n",
    "            else:\n",
    "                high = mid - 10 ** -6\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAchieve(self, buckets, x, loss):\n",
    "        total_lost = 0\n",
    "        total_extra = 0\n",
    "        for water in buckets:\n",
    "            if water > x:\n",
    "                total_extra += water - x\n",
    "            else:\n",
    "                total_lost += x - water\n",
    "        return total_extra * (1 - loss / 100.0) >= total_lost\n",
    "\n",
    "    def equalizeWater(self, buckets, loss):\n",
    "        low, high = 0, max(buckets)\n",
    "        while high - low > 1e-6:\n",
    "            mid = (low + high) / 2.0\n",
    "            if self.canAchieve(buckets, mid, loss):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return low\n",
    "\n",
    "# 在 LeetCode 上不需要下面的示例代码，但是你可以在本地运行来测试。\n",
    "# 示例\n",
    "# sol = Solution()\n",
    "# buckets = [5,7,3,2]\n",
    "# loss = 10\n",
    "# print(sol.equalizeWater(buckets, loss))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n, l, r = len(buckets), 0, max(buckets)\n",
    "\n",
    "        def helper(x):\n",
    "            s1 = s2 = 0\n",
    "            for b in buckets:\n",
    "                if b > x:\n",
    "                    # 倒掉了多少水\n",
    "                    s1 += b - x\n",
    "                else:\n",
    "                    # 至少需要多少水\n",
    "                    s2 += (x - b) * 100 / (100 - loss)\n",
    "\n",
    "            return s1 >= s2\n",
    "\n",
    "\n",
    "        while (r - l) > 1e-5:\n",
    "            mid = (l + r) / 2\n",
    "            if helper(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 0.000001\n",
    "\n",
    "        return l\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n = len(buckets)\n",
    "        s = sum(buckets)\n",
    "        if loss == 0:\n",
    "            return s / n\n",
    "        \n",
    "        def check(x):\n",
    "            pour_out = 0\n",
    "            pour_in = 0\n",
    "            for i in buckets:\n",
    "                if i < x:\n",
    "                    pour_in += x - i \n",
    "                else:\n",
    "                    pour_out += i - x \n",
    "            return pour_out * (1 - loss / 100) >= pour_in\n",
    "        \n",
    "        low, high = min(buckets), s / n \n",
    "        ans = low \n",
    "        while low <= high - 10 ** -5:\n",
    "            mid = (low + high) / 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 10 ** -10\n",
    "            else:\n",
    "                high = mid - 10 ** -10\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n = len(buckets)\n",
    "        tot = sum(buckets)\n",
    "        l, r = 0, tot / n\n",
    "        eps = 10 ** (-6)\n",
    "        \n",
    "        def check(x):\n",
    "            a = b = 0 \n",
    "            \n",
    "            for i in buckets:\n",
    "                if i >= x:\n",
    "                    a += i - x \n",
    "                else:\n",
    "                    b += (x - i) / (100 - loss) * 100\n",
    "            if a >= b:\n",
    "                return True \n",
    "            return False \n",
    "        \n",
    "        while r - l > eps:\n",
    "            mid = (l + r) / 2 \n",
    "            if check(mid):\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid \n",
    "        return r\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        if len(buckets)==1:\n",
    "            return buckets[0]\n",
    "        left,right=min(buckets),max(buckets)\n",
    "        while left+10**-5<right:\n",
    "            middle=(left+right)/2\n",
    "            bigger=list(filter(lambda x:x>=middle,buckets))\n",
    "            smaller=list(filter(lambda x:x<middle,buckets))\n",
    "            if (sum(bigger)-len(bigger)*middle)*(1-loss/100)==(len(smaller)*middle-sum(smaller)):\n",
    "                return middle\n",
    "            elif (sum(bigger)-len(bigger)*middle)*(1-loss/100)>(len(smaller)*middle-sum(smaller)):\n",
    "                left=middle\n",
    "            else:\n",
    "                right=middle\n",
    "        return left\n",
    "if __name__ == '__main__':\n",
    "    Solution().equalizeWater([1,2,7],80)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n = len(buckets)\n",
    "        sums = sum(buckets) # initial total water volume \n",
    "        l, r = 0, sums/n\n",
    "        eps = 10**(-5)\n",
    "\n",
    "        def check(x):\n",
    "            a = b = 0\n",
    "            for i in buckets:\n",
    "                if i >= x:\n",
    "                    a += (i - x)*(1 - 0.01*loss) # water poured\n",
    "                else:\n",
    "                    b += x - i # water needed\n",
    "            return a >= b\n",
    "        \n",
    "        while r > l + eps:\n",
    "            mid = (r + l) / 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n = len(buckets)\n",
    "        t = (100 - loss) / 100\n",
    "        # 能量损失只计算一遍\n",
    "        def check(mid):\n",
    "            s = 0\n",
    "            for x in buckets:\n",
    "                if x >= mid:\n",
    "                    s += (x - mid) * t\n",
    "                else:\n",
    "                    s -= (mid - x)\n",
    "            return s >= 0\n",
    "\n",
    "        l, r = min(buckets), max(buckets)\n",
    "        while r - l > 0.000001:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n = len(buckets)\n",
    "        t = (100 - loss) / 100\n",
    "        # 能量损失只计算一遍\n",
    "        def check(mid):\n",
    "            s = 0\n",
    "            for x in buckets:\n",
    "                if x >= mid:\n",
    "                    s += (x - mid) * t\n",
    "                else:\n",
    "                    s -= (mid - x)\n",
    "            return s >= 0\n",
    "\n",
    "        l, r = min(buckets), max(buckets)\n",
    "        for _ in range(32):\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        def check(v):\n",
    "            a = b = 0\n",
    "            for x in buckets:\n",
    "                if x >= v:\n",
    "                    a += x - v\n",
    "                else:\n",
    "                    b += (v - x) * 100 / (100 - loss)\n",
    "            return a >= b \n",
    "\n",
    "        l, r = 0, max(buckets)\n",
    "        while r - l > 1e-5:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        if len(buckets)==1:\n",
    "            return buckets[0]\n",
    "        left,right=min(buckets),max(buckets)\n",
    "        while left+10**-5<right:\n",
    "            middle=(left+right)/2\n",
    "            bigger=list(filter(lambda x:x>=middle,buckets))\n",
    "            smaller=list(filter(lambda x:x<middle,buckets))\n",
    "            if (sum(bigger)-len(bigger)*middle)*(1-loss/100)==(len(smaller)*middle-sum(smaller)):\n",
    "                return middle\n",
    "            elif (sum(bigger)-len(bigger)*middle)*(1-loss/100)>(len(smaller)*middle-sum(smaller)):\n",
    "                left=middle\n",
    "            else:\n",
    "                right=middle\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        n = len(buckets)\n",
    "        s = sum(buckets)\n",
    "        if loss == 0:\n",
    "            return s / n\n",
    "        \n",
    "        def check(x):\n",
    "            pour_out = 0\n",
    "            pour_in = 0\n",
    "            for i in buckets:\n",
    "                if i < x:\n",
    "                    pour_in += x - i \n",
    "                else:\n",
    "                    pour_out += i - x \n",
    "            return pour_out * (1 - loss / 100) >= pour_in\n",
    "        \n",
    "        low, high = min(buckets), s / n \n",
    "        ans = low \n",
    "        while low <= high - 10 ** -5:\n",
    "            mid = (low + high) / 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 10 ** -6\n",
    "            else:\n",
    "                high = mid - 10 ** -6\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalizeWater(self, buckets: List[int], loss: int) -> float:\n",
    "        l, r = min(buckets),sum(buckets)/len(buckets)\n",
    "        eps = 10 ** (-5)\n",
    "        while r - l > eps:\n",
    "            mid = (l + r) / 2 \n",
    "            s=0\n",
    "            for i in buckets:\n",
    "                if i >= mid:\n",
    "                    s += i - mid\n",
    "                else:\n",
    "                    s-= (mid - i) / (100 - loss) * 100\n",
    "            if s>=0:\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        return r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
